home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / planar_m.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.5 KB  |  177 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  planar_map.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef PLANAR_MAPH
  19. #define PLANAR_MAPH
  20.  
  21. #include <LEDA/graph.h>
  22.  
  23. class i_face;
  24.  
  25. typedef i_face* face;
  26.  
  27. class i_face {
  28.  
  29. friend class planar_map;
  30.  
  31.  edge      head;  // first edge of face
  32.  list_item loc;   // location in F_list
  33.  ent       inf;   // user defined information
  34.  
  35.  planar_map*  g;     // face of (*g)
  36.  
  37.  
  38. friend planar_map* graph_of(face f) { return f->g; }
  39.  
  40.  
  41.  i_face(ent x, planar_map* G) 
  42.  { 
  43.    inf = x ; 
  44.    head = nil; 
  45.    loc = nil; 
  46.    g = G;
  47.   }
  48.  
  49.  
  50. OPERATOR_NEW(4)
  51. OPERATOR_DEL(4)
  52.  
  53. };
  54.  
  55. declare(list,face);
  56.  
  57. declare(node_array,int)
  58.  
  59. class planar_map : public graph {
  60.  
  61. list(face)       F_list;
  62.  
  63. face  new_face(ent i=0);
  64. void  del_face(face f) { F_list.del(f->loc); delete f; }
  65. face& get_face(edge e) { return (face&)(e->contents);  }
  66. edge& get_rev(edge e)  { return (edge&)(e->adj_loc2);  }
  67.  
  68. virtual void copy_face_entry(ent& x)  const {x=x;}
  69. virtual void init_face_entry(ent& x)  const {x=0;}
  70. virtual void clear_face_entry(ent& x) const {x=0;}
  71. virtual void print_face_entry(ent& x) const {x=x;}
  72.  
  73. public:
  74.  
  75.  
  76.  planar_map(const graph&);
  77. ~planar_map();
  78.  
  79. void       init_entries();
  80.  
  81.  
  82. list(node) adj_nodes(face)   const;
  83. list(node) adj_nodes(node v) const { return graph::adj_nodes(v); }
  84.  
  85. list(edge) adj_edges(face)   const;
  86. list(edge) adj_edges(node v) const { return graph::adj_edges(v); }
  87.  
  88. list(face) all_faces()       const { return F_list; }
  89. list(face) adj_faces(node)   const;
  90.  
  91. face       adj_face(edge e)  const { return face(e->contents); }
  92.  
  93. list(edge) triangulate();
  94.  
  95. edge reverse(edge e)         const { return edge(e->adj_loc2); }
  96.  
  97. edge first_face_edge(face f) const { return f->head; }
  98. edge succ_face_edge(edge e)  const { return cyclic_adj_succ(reverse(e)); } 
  99. edge pred_face_edge(edge e)  const { return reverse(cyclic_adj_pred(e)); } 
  100.  
  101. edge next_face_edge(edge e)  const  
  102. { e = succ_face_edge(e);
  103.   return (e==adj_face(e)->head) ? nil : e;
  104. }
  105.  
  106. face first_face() const { return F_list.head(); }
  107.  
  108. face next_face(face f) const
  109. { list_item it = F_list.succ(f->loc);
  110.   return (it) ? F_list.contents(it) : nil;
  111. }
  112.  
  113.  
  114. edge       new_edge(edge,edge,ent=0);
  115. void       del_edge(edge,ent=0);
  116.  
  117. ent&       entry(face f)         { return f->inf;          }
  118. ent        inf(face f)     const { return f->inf;   }
  119. ent&       entry(node v)         { return graph::entry(v); }
  120. ent        inf(node v)     const { return graph::inf(v); }
  121.  
  122. int  straight_line_embedding(node_array(int)&, node_array(int)&);
  123.  
  124. };
  125.  
  126.  
  127. //------------------------------------------------------------------------------
  128. // PLANAR_MAP: generic planar map
  129. //------------------------------------------------------------------------------
  130.  
  131. #define PLANAR_MAP(vtype,ftype)   name3(vtype,ftype,PLANAR_MAP)
  132.  
  133. #define PLANAR_MAPdeclare2(vtype,ftype)\
  134. \
  135. class PLANAR_MAP(vtype,ftype) : public planar_map {\
  136. \
  137. void init_node_entry(ent& x)  const { vtype y=0; x = Copy(y); }\
  138. void init_face_entry(ent& x)  const { ftype y=0; x = Copy(y); }\
  139. \
  140. void copy_node_entry(ent& x)  const { Copy(*(vtype*)&x); }\
  141. void copy_face_entry(ent& x)  const { Copy(*(ftype*)&x); }\
  142. \
  143. void clear_node_entry(ent& x) const { Clear(*(vtype*)&x); }\
  144. void clear_face_entry(ent& x) const { Clear(*(ftype*)&x); }\
  145. \
  146. public:\
  147. \
  148.    vtype  inf(node v)         const   { return vtype(planar_map::inf(v)); }\
  149.    ftype  inf(face f)         const   { return ftype(planar_map::inf(f)); }\
  150.    vtype& entry(node v)          { return *(vtype*)&(planar_map::entry(v)); }\
  151.    ftype& entry(face f)          { return *(ftype*)&(planar_map::entry(f)); }\
  152.    vtype& operator[] (node v)    { return entry(v); }\
  153.    ftype& operator[] (face f)    { return entry(f); }\
  154. \
  155.    edge   new_edge(edge e1, edge e2)\
  156.                           { return planar_map::new_edge(e1,e2,0); }\
  157.    edge   new_edge(edge e1, edge e2, ftype a)\
  158.                           { return planar_map::new_edge(e1,e2,Ent(a)); }\
  159. \
  160. void print_node(node v) const { cout << "["; Print((vtype&)(entry(v))); cout << "]";}\
  161. \
  162.    PLANAR_MAP(vtype,ftype)(const GRAPH(vtype,ftype)& G) : ((graph&)G)   {}\
  163.    ~PLANAR_MAP(vtype,ftype)()     { clear(); }\
  164. \
  165. };
  166.  
  167.  
  168. #define forall_face_edges(e,F)\
  169. for(e=graph_of(F)->first_face_edge(F); e; e=graph_of(F)->next_face_edge(e)) 
  170.  
  171. #define forall_faces(f,G)\
  172. for(f=G.first_face(); f; f=G.next_face(f)) 
  173.  
  174.  
  175.  
  176. #endif PLANAR_MAPH
  177.